package pri.hillchen.algorithm.array;

import java.util.HashSet;
import java.util.Set;

/**
 * Created by hillchen on 2017/10/9 0009.
 */
public class MaxContinuousSubSum {
    public static MaxSubSumRet maxContinuousSubSum(int[] arrays){
        int currentStart = 0;
        Set<SubSet> currSubSets = new HashSet<>();
        currSubSets.add(new SubSet());
        Set<SubSet> maxSubSets = new HashSet<>();
        long sum = 0;
        long maxSum = 0;

        for(int i=0;i<arrays.length;i++){
           if(arrays[i] >0){
               for(SubSet subSet : currSubSets){
                   subSet.endIndex = i;
               }
               if(sum == maxSum){
                   sum += arrays[i];
                   maxSum += arrays[i];
               }else{
                   sum += arrays[i];
                   if(sum == maxSum){
                       maxSubSets.addAll(currSubSets);
                   }else if(sum > maxSum){
                       maxSubSets.clear();
                       maxSubSets.addAll(currSubSets);
                       maxSum = sum;
                   }
               }

           }else if(arrays[i] == 0 ){
               SubSet subSet = new SubSet();
               subSet.startIndex = currentStart;
               subSet.endIndex = i;
               currSubSets.add(subSet);
               if(sum == 0){
                   currentStart = i+1;
               }
           }else{
               if(sum == maxSum){
                   maxSubSets.addAll(currSubSets);
               }
               sum += arrays[i];
               if(sum < 0){
                   currentStart = i+1;
                   currSubSets.clear();
                   SubSet subSet = new SubSet();
                   subSet.startIndex = currentStart;
                   subSet.endIndex = currentStart;
                   currSubSets.add(subSet);
               }else if(sum == 0){
                   currentStart = i+1;
                   SubSet subSet = new SubSet();
                   subSet.startIndex = currentStart;
                   subSet.endIndex = currentStart;
                   currSubSets.add(subSet);
               }else{
                   for(SubSet subSet : currSubSets){
                       subSet.endIndex = i;
                   }
               }
           }
        }

        if(maxSum == sum){
            maxSubSets.addAll(currSubSets);
        }
        MaxSubSumRet maxSubSumRet = new MaxSubSumRet();
        maxSubSumRet.maxSum = maxSum;
        maxSubSumRet.subSum = maxSubSets;
        return maxSubSumRet;
    }

    public static class SubSet{
        int startIndex = 0;
        int endIndex = 0;

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            SubSet subSet = (SubSet) o;

            if (startIndex != subSet.startIndex) return false;
            return endIndex == subSet.endIndex;

        }

        @Override
        public int hashCode() {
            int result = startIndex;
            result = 31 * result + endIndex;
            return result;
        }
    }
    public static class MaxSubSumRet{
        private long maxSum = 0;
        private Set<SubSet> subSum = new HashSet<>();
    }

    public static void main(String[] args){
        int[] arrays = {0,0,0,4,5,6,-4,-5,-6,0,0,4,5,6};
        MaxSubSumRet maxSubSumRet = maxContinuousSubSum(arrays);
        System.out.println(maxSubSumRet.maxSum);
        for(SubSet subSet : maxSubSumRet.subSum){
            System.out.println("startIndex:"+subSet.startIndex+",endIndex:"+subSet.endIndex);
        }
    }
}
